//二叉搜索树
class BinarySearchTree {
    static class TreeNode {
       public TreeNode left;//左边
       public TreeNode right;//右边
       public int val;//数值域

       public TreeNode(int val){
          this.val = val;
       }
    }

    public TreeNode root = null;//根节点

    //查找val值是不是在当前的搜索树当中
    public TreeNode Search(int val) {
        TreeNode cur = root;
        //为空则说明树中没有val值
        while (cur != null) {
            if (val > cur.val) {
                //说明val值在右边
                cur = cur.right;//cur往右走
            }else if(val < cur.val){
                //val值在左边
                cur = cur.left;//cur往左走
            }else {
                //找到了
                return cur;//返回存放val值的结点
            }
        }
        //找不到了
        return null;
    }

    //插入元素key
    public boolean insert(int key) {
        if (root == null) {
            //树为空，直接插入
            root = new TreeNode(key);
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (key > cur.val) {
                //cur要往右边走
                parent = cur;//cur走之前让parent指向cur
                cur = cur.right;
            } else if (key < cur.val) {
                //cur要往左走
                parent = cur;
                cur = cur.left;
            } else {
                //相同的可以不能插入
                return false;
            }
        }
        //cur此时为空了
        TreeNode node = new TreeNode(key);//新节点
        if (key > parent.val) {
            //往右边插
            parent.right = node;
        }else {
            //往左边插
            parent.left = node;
        }
        return true;
    }

    //写一个中序遍历来测试插入是否正确
    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    //删除
    public void remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        if (root == null) {
            return;
        }
        while (cur != null) {
            if (cur.val == key) {
                //找到了要删除的 - 开始删除
                removeNode(parent, cur);//调用方法删除
            } else if (cur.val > key) {
                //cur往左边走
                parent = cur;//走之前parent指向cur
                cur= cur.left;
            } else {
                //cur往右边走
                parent = cur;//走之前parent指向cur
                cur = cur.right;
            }
        }
    }

    //删除的方法
    public void removeNode(TreeNode parent, TreeNode cur) {
        //分三种情况
        if (cur.left == null) {
            //左边为空
            if (cur == root) {
                //要删根节点
                root = cur.right;
            } else if (cur == parent.left){
                //cur在左边
                parent.left = cur.right;
            } else {
                //cur在右边
                parent.left = cur.right;
            }
        } else if (cur.right == null) {
            //右边为空
            if (cur == root) {
                //删除根节点
                root = cur.right;
            } else if (cur == parent.left) {
                //cur在左边
                parent.left = cur.left;
            } else {
                //cur在右边
                parent.right = cur.left;
            }
        } else {
            //左右都不为空
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }
}
public class Search {
   public static void main(String[] args) {
       BinarySearchTree binarySearchTree = new BinarySearchTree();
       int[] array = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9};
       for (int i = 0; i < array.length; i++) {
           binarySearchTree.insert(array[i]);

       }
       binarySearchTree.inorder(binarySearchTree.root);
       System.out.println("hello");
   }
}
